package midalgorithms.arrandstr;

import java.util.*;

public class _01ThreeSum {
    public static List<List<Integer>> threeSum(int[] nums) {
        //  存在 a + b + c = 0 ? ==> 存在 a + b = -c ?
        int len = nums.length;
        if (len < 3){
            return new ArrayList<>();
        }
        final int TARGET = 0;
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int boundary = 0;boundary < len - 2;boundary++){
            if (boundary > 0 && nums[boundary] == nums[boundary-1]){
                continue;
            }
            int target = TARGET - nums[boundary];
            int right = len - 1;
            /**
             * 逻辑说不通
            while (left + 1 < right && nums[left] == nums[left+1]){
                left++;
            }
            while (right - 1 > left && nums[right] == nums[right-1]){
                right--;
            }
            */
            for (int left = boundary + 1;left < len - 1;left++){
                if (left > boundary + 1 && nums[left] == nums[left-1]){
                    continue;
                }
                while (left < right && nums[left] + nums[right] > target){
                    right--;
                }
                if (left == right){
                    break;
                }
                //这种方法的好处是right的左移适可而止，不会添加重复的元素！
                if (nums[left] + nums[right] == target){
                    List<Integer> list = new ArrayList<>(3);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    list.add(nums[boundary]);
                    res.add(list);
                }
            }
        }
        return res;
    }
}
